#include <iostream>
#include <vector>
using namespace std;
class Solution {
 public:
  vector<int> path;
  vector<vector<int> > ans;
  vector<vector<int> > combine(int n, int k) {
    backtracking(1, n, k);
    return ans;
  }
  void backtracking(int start_index, int n, int k) {
    // 到达叶子结点或条件满足时，递归终止
    if (path.size() == k) {  // 树的深度
      ans.push_back(path);
      return;
    }
    // 为什么要有这个startIndex呢？
    // 每次从集合中选取元素，可选择的范围随着选择的进行而收缩，
    // 调整可选择的范围，就是要靠startIndex。
    // 所以需要startIndex来记录下一层递归，搜索的起始位置。
    // for (int i = start_index; i <= n; i++) {  // 树的宽度
    for (int i = start_index; i <= n - (k - path.size()) + 1;
         i++)  // i为本次搜索的起始位置
      path.push_back(i);
    backtracking(i + 1, n, k);  // i+1是因为每个数只能选一遍
    path.pop_back();
  }
};